#include <iostream>

using namespace std;

template <typename T>
void insertionSort(T arr[], size_t begin, size_t end){
	T temp;
	for(size_t i = begin + 1; i <= end; i ++){
		temp = arr[i];
		size_t j = i - 1;
		for(; j >= 0; j --){
			if(arr[j] <= temp)
				break;
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = temp;
	}
}

void testInsertionSort(){
	// int arr[] = {3, 2, 5, 6, 9, 1, 4, 8, 10, 12};
	int arr[] = {4, 1, 1, 2, 1, 1, 1};
	int size = sizeof(arr) / sizeof(int);
	insertionSort(arr, 0, size - 1);

	int index = 0;
	while(index < size)
		cout << arr[index ++] << endl;
	getchar();
}